/*
 【基础】经典递归问题——汉诺塔 (使用递归的方法求解)
  题目描述
    汉诺塔（又称河内塔）问题是印度的一个古老的传说。
    开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，
    第一根上面套着 64 个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，
    庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，
    但每次只能搬一个，而且大的不能放在小的上面。

    面对庞大的数字 (移动圆片的次数) 18446744073709551615，看来，众僧们耗尽毕生精力也不可能完成金片的移动。

              │               │              │
              │               │              │
            ┌─┼─┐             │              │
           ┌┴─┼─┴┐            │              │
          ┌┴──┼──┴┐           │              │
        ──┴───┴───┴───────────┴──────────────┴─────
              A               B              C

    后来，这个传说就演变为汉诺塔游戏:
      1. 有三根杆子 A,B,C。A 杆上有若干碟子
      2. 每次移动一块碟子, 小的只能叠在大的上面
      3. 把所有碟子从 A 杆全部移到C杆上
    经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动金片：
      如 3 阶汉诺塔的移动：A → C, A → B, C → B, A → C, B → A, B → C, A → C
    此外，汉诺塔问题也是程序设计中的经典递归问题。

    算法思路：
      1. 如果只有一个金片，则把该金片从源移动到目标棒，结束。
      2. 如果有 n 个金片，则把前 n-1 个金片移动到辅助的棒，然后把自己移动到目标棒，最后再把前 n-1 个移动到目标棒.
  输入
    一个整数 N，表示 A 柱上有 N 个碟子。（0 < n <= 10）
  输出
    若干行，即移动的最少步骤
  样例输入
    3
  样例输出
    A To C
    A To B
    C To B
    A To C
    B To A
    B To C
    A To C
*/

#include <bits/stdc++.h>

using namespace std;

// 函数功能:
//   把 n 个盘子从变量 a 代表的柱子挪到变量 c 代表的柱子上，中间我们可以借助变量 b 代表的柱子，
//   并输出每一步的具体过程
// 参数说明:
//   参数 n 表示要挪动的盘子的个数;
//   参数 a 表示初始柱，参数 b 表示中间柱 ，参数 c 表示目标柱
void f(int n, char a, char b, char c) {
    if (n == 1) {
        cout << a << " To " << c << endl;
    } else {
        f(n - 1, a, c, b); // 将 n-1 个盘子从变量 a 代表的柱子挪到变量 b 代表的柱子上
        f(1, a, b, c);     // 把 1   个盘子从变量 a 代表的柱子挪到变量 c 代表的柱子上
        f(n - 1, b, a, c); // 把 n-1 个盘子从变量 b 代表的柱子挪到变量 c 代表的柱子上
    }
}

int main() {
    int n;

    cin >> n;
    f(n, 'A', 'B', 'C'); // 把 n 个盘子从 A 柱挪到 C 柱，可借助 B 柱

    return 0;
}